package leetcode.editor.cn;

//反转一个单链表。 
//
// 示例: 
//
// 输入: 1->2->3->4->5->NULL
//输出: 5->4->3->2->1->NULL 
//
// 进阶: 
//你可以迭代或递归地反转链表。你能否用两种方法解决这道题？ 
// Related Topics 链表 
// 👍 1569 👎 0


import leetcode.editor.cn.basic.ListNode;

public class ReverseLinkedList {
    public static void main(String[] args) {
        Solution solution = new ReverseLinkedList().new Solution();
        ListNode node = new ListNode().add(1, 2, 3, 4, 5);
        System.out.println(solution.reverseList3(node));
//        System.out.println(Arrays.toString(solution.myReverse(node, getTail(node))));
    }

    private static ListNode getTail(ListNode node) {

        if (node == null || node.next == null) {
            return node;
        }
        return getTail(node.next);
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {

        /**
         * 自己写的递归反转
         * // 输入: 1->2->3->4->5->NULL
         * //输出: 5->4->3->2->1->NULL
         * 思路
         *
         *
         * @param head
         * @return
         */
        public ListNode reverseList2(ListNode head) {
            if (head == null || head.next == null) return head;
            ListNode node = reverseList2(head.next);
            head.next.next = head;
            head.next = null;
            return node;
        }

        /**
         * 在遍历列表时，将当前节点的 \textit{next}next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用！
         * 1->2->3
         * @param head
         * @return
         */
        public ListNode reverseList3(ListNode head) {
            ListNode prev = null;
            // 当前节点指针
            ListNode curr = head;
            while (curr != null) {
                // 当前节点的next节点的指针
                ListNode nextTemp = curr.next;
                // 把当前单独节点剥离 指向prev     1 -> null(prev)
                curr.next = prev;
                // prev 往左移一格     prev -> 1
                prev = curr;
                // 当前节点指针往右移一格
                curr = nextTemp;
            }
            return prev;
        }

        public ListNode[] myReverse(ListNode head, ListNode tail) {
            ListNode prev = tail.next;
            ListNode p = head;
            while (prev != tail) {
                ListNode nex = p.next;
                p.next = prev;
                prev = p;
                p = nex;
            }
            return new ListNode[]{tail, head};
        }


        /**
         * // 输入: 1->2->3->4->5->NULL
         * //输出: 5->4->3->2->1->NULL
         * @param head
         * @return
         */
//    public ListNode reverseList(ListNode head) {
//        Stack<Integer> stack = new Stack();
//        while (head != null) {
//            stack.push(head.val);
//            head = head.next;
//        }
//        ListNode node = new ListNode();
//        ListNode curr = node;
//        while (stack.size() != 0){
//            int val = stack.pop();
//            node.next = new ListNode(val);
//            node = node.next;
//        }
//        return curr.next;
//
//    }

        /**
         * // 输入: 1->2->3->4->5->NULL
         * //输出: 5->4->3->2->1->NULL
         *
         * 递归的思路是 反正指针   1 -> 2  变为  2 -> 1   node.next = node1 , node1.next=node , 合起来 node.next.next = node;(循环了),
         * 接着取消 node.next = null ,  最终实现反转
         *
         * @param head
         * @return
         */
        public ListNode reverseList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            // head=1  head.next=2  head.next.next=3
            ListNode newHead = reverseList(head.next);
            // 这里的含义是
            /**
             * 也就是 node1.next = node2，
             *
             * 然后把 2 指向 1：node2.next = node1
             *
             * 合起来就是：node1.next.next = node1
             */
            //  1 -> 2   1-> 2 -> 1
            head.next.next = head;
            // node1 不指向 node2了     1 ->(移除指针)  2 -> 1
            head.next = null;
            return newHead;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}